package day_2022_4_to_7.nowcoder;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 字符串的排列
 * @author haomin
 * @date 2022/05/05 19:38
 **/

public class Permutation_22f {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<>();
        // 如果字符串不为空进行后续的操作
        if(str != null || str.length() != 0){
            PermutationHelper(str.toCharArray(),0,result);
            // 按字典序排列
            Collections.sort(result);
        }
        return result;
    }

    private void PermutationHelper(char[] str, int start,ArrayList<String> result) {
        // 如果start为末尾索引，就是走到最后一个字符，说明已经得到了一个排列后的字符串，判断是否符合要求，然后return
        if(start == str.length - 1){
            // 判断result中是否已经存在当前的字符串
            if(!isExist(str,result)){
                // 如果result中不存在存在当前字符串，进行添加操作
                result.add(new String(str));
            }
            return;
        }

        // 1.让每个字符都要做一遍开头(fori遍历)
        for (int i = start; i < str.length; i++) {
            // 第一层 分别以 a,b,c 为根节点
            swap(str,i,start);
            // 2.然后在求解子问题(子问题中也是让start+1开始的字符都要做一遍开头(fori遍历))
            PermutationHelper(str,start+1,result);

            // 在进行后续遍历之前，要把刚刚已经改变的str还原
            swap(str,i,start);
        }
    }

    // 交换三连
    private void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }

    // 判断result中是否已经存在当前的字符串
    private boolean isExist(char[] str, ArrayList<String> result) {
        return result.contains(String.valueOf(str));
    }
}